import java.util.Stack;

/**
 * @Author YuanYuan
 * @Date 2022/7/25
 * @Time 18:08
 */
public class Sort {
    public void bubbleSort(int[] arr) {

        for (int i = 0; i < arr.length-1; i++) {
            boolean flag = false;
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j] >arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag = true;
                }
            }
            if(!flag) {
                break;
            }
        }
        return;
    }
    public void insertSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int end = arr[i];
            int j = 0;
            for (j = i-1; j >=0 ; j--) {
                if(arr[j] > end) {
                    arr[j+1] = arr[j];
                }else {
                    break;
                }
            }
            arr[j+1] = end;
        }
    }


    public void selectSort(int[] arr) {

        for (int i = 0; i < arr.length; i++) {
            int min = i;
            for (int j = i; j < arr.length; j++) {
                if(arr[j]<arr[min]) {
                    min = j;
                }
            }
            swap(arr,i,min);
        }
    }
    public void fastselectSort(int[] arr) {
        int len = arr.length;
        int left = 0;
        int right = len-1;
        while(left<=right) {
            int min = left;
            int max = right;
            for (int i = left; i < right+1; i++) {
                if(arr[i]<arr[min]) {
                    min = i;
                }
                if(arr[i]>arr[max]) {
                    max = i;
                }
            }
            swap(arr,min,left++);
            if(left-1 == max) {
                max = min;
            }
            swap(arr,max,right--);
        }
    }
    private void swap(int[] arr,int a,int b) {
        int temp =  arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
    private int onequickSort(int[] arr,int left,int right) {
        int cur = left;
        while(left<right) {
            while(left<right&&arr[right]>=arr[cur]) {
                right--;
            }
            while (left<right&&arr[left]<=arr[cur]) {
                left++;
            }
            swap(arr,left,right);
        }
        swap(arr,left,cur);
        return left;
    }
    private void quick(int[] arr,int left,int right) {
        if(left >= right) {
            return;
        }
        int index = midIndex(arr,left,right);
        swap(arr,index,left);
        int src = onequickSort(arr,left,right);
        quick(arr,left,src-1);
        quick(arr,src+1,right);
    }
    private void quick1(int[] arr,int left,int right) {
        if(left >= right) {
            return;
        }
        if(right-left<15) {
            insertSort(arr);
            return;
        }
        int index = midIndex(arr,left,right);
        swap(arr,index,left);
        int src = onequickSort(arr,left,right);
        quick(arr,left,src-1);
        quick(arr,src+1,right);
    }

    public void quickSort(int[] arr) {
        int left = 0;
        int right = arr.length-1;
        quick1(arr,left,right);
    }
    /**
     * @return void
     * 挖坑法
    */
    public void holeQuickSort(int[] arr) {
        int left = 0;
        int right = arr.length-1;
        holeQuick(arr,left,right);
    }
    private int oneHoleQuickSort(int[] arr,int left,int right) {
        int cur = arr[left];
        while(left<right) {
            while(left<right&&arr[right]>=cur) {
                right--;
            }
            arr[left] = arr[right];
            while (left<right&&arr[left]<=cur) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = cur;
        return left;
    }
    private void holeQuick(int[] arr,int left,int right) {
        if(left >= right) {
            return;
        }
        int src = oneHoleQuickSort(arr,left,right);
        holeQuick(arr,left,src-1);
        holeQuick(arr,src+1,right);
    }
    /**
     * @return void
     * 双指针法
    */
    public void doubleQuickSort(int[] arr) {
        int left = 0;
        int right = arr.length-1;
        holeQuick(arr,left,right);
    }
    private void doubleQuick(int[] arr,int left,int right) {
        if(left >= right) {
            return;
        }
        int src = oneDoubleQuickSort(arr,left,right);
        doubleQuick(arr,left,src-1);
        doubleQuick(arr,src+1,right);
    }
    private int oneDoubleQuickSort(int[] arr,int left,int right) {
        int key = left;
        int cur = left+1;
        int prev = left;
        while(cur<right) {
            if(arr[cur]<=arr[key]&&arr[++prev]!=arr[cur]) {
                swap(arr,cur,prev);
            }
            cur++;
        }
        swap(arr,prev,key);
        return prev;
    }
    private int midIndex(int[] arr,int left,int right) {
        int mid = (left+right)/2;
        if(arr[left]>=arr[right]) {
            if(arr[right]>=arr[mid]) {
                return right;
            }else if (arr[left]<=arr[mid]){
                return left;
            }else {
                return mid;
            }
        }else {
            if(arr[left]>=arr[mid]) {
                return left;
            }else if(arr[right] <= arr[mid]){
                return right;
            }else {
                return mid;
            }
        }
    }
    public void stackQuick(int[] arr) {
        int left = 0;
        int right = arr.length-1;
        int src = oneHoleQuickSort(arr,left,right);
        Stack<Integer> stack = new Stack<>();
        if(src-left>1) {
            //先把右边放进去
            stack.push(src-1);
            stack.push(left);
        }
        if(right-src>1) {
            stack.push(right);
            stack.push(src+1);
        }
        while(!stack.isEmpty()) {
            left = stack.pop();
            right = stack.pop();
            src = oneHoleQuickSort(arr,left,right);
            if(src-left>1) {
                //先把右边放进去
                stack.push(src-1);
                stack.push(left);
            }
            if(right-src>1) {
                stack.push(right);
                stack.push(src+1);
            }
        }
    }
}
